package leetcode_200;

import java.util.Arrays;

/**
 *@author 周杨
 *TwoSumII_InputArrayIsSorted_167_  给定一个有序数组 找到这个数组中 2个相加等于target的数的索引
 *describe:用Arrays.binarySearch方法 如果找不到 则给出插入位置  这样就能缩小范围 不用第二次遍历 AC 99%
 *2018年6月8日 下午3:41:22
 */
public class TwoSumII_InputArrayIsSorted_167_ {

	public static void main(String[] args) {
		TwoSumII_InputArrayIsSorted_167_ test=new TwoSumII_InputArrayIsSorted_167_();
		int [] array=new int[] {1,2,3,6,7};
		System.out.println(Arrays.binarySearch(array, 4));

	}
	
	public int[] twoSum(int[] numbers, int target) {
        int[] res=new int[2];
        for(int i=0;i<numbers.length;++i) {
        	for(int j=i+1;j<numbers.length;++j) {
        		if(numbers[i]+numbers[j]==target) {
        			res[0]=i+1;
        			res[1]=j+1;
        		}
        		if(numbers[i]+numbers[j]>target)
        			break;
        	}
        }
        return res;
    }
	
	/**
	 * describe:用二分搜索 若找到 返回索引 若未找到 返回要（插入的坐标* -1） -1  这样能保证每次找到的索引 left和right相加刚好等于target这样就无限缩小了空间
	 * 2018年6月8日 下午3:21:49
	 */
	public int[] twoSum1(int[] numbers, int target) {
        boolean isBegin = true;
        int [] result = new int [2];
        int temp = 0, before = 0, end = numbers.length, index = 0;
        while(before<end){
            if(isBegin){
                temp = target - numbers[before];//每次去找与开头结合
                index = Arrays.binarySearch(numbers, before, end, temp);
                if(index > 0){//找到了
                    result[0] = before + 1;
                    result[1] = index + 1;
                    return result;
                }else{
                    end = -index - 1 - 1;//插入点
                    isBegin = false;
                }
            }else{
                temp = target - numbers[end];//找与尾的结合
                index = Arrays.binarySearch(numbers, before, end, temp);
                if(index > 0){
                    result[0] = index + 1;
                    result[1] = end + 1;
                    return result;
                }else{
                    before = -index - 1;
                    isBegin = true;
                }
            }
        }
    return result;
    }

}
